package day06;

/**
 * @author aiPlusPlus
 * @version 1.0
 * @date 2023/1/6 9:35
 */

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
 *
 * 示例:
 *
 * 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
 * 输出: [3,3,5,5,6,7]
 * 解释:
 *
 *   滑动窗口的位置                最大值
 * ---------------               -----
 * [1  3  -1] -3  5  3  6  7       3
 *  1 [3  -1  -3] 5  3  6  7       3
 *  1  3 [-1  -3  5] 3  6  7       5
 *  1  3  -1 [-3  5  3] 6  7       5
 *  1  3  -1  -3 [5  3  6] 7       6
 *  1  3  -1  -3  5 [3  6  7]      7
 */
public class Solution2 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int left = 0,right = k-1;
        LinkedList<Integer> list = new LinkedList<>();
        for (int i = 0; i <= right; i++) {
            if(!list.isEmpty()){
                while (!list.isEmpty()&&nums[i]>=nums[list.peekLast()]){
                    list.pollLast();
                }
            }
            list.addLast(i);
        }
        List<Integer> ans = new ArrayList<>();
        while (right<nums.length){
            ans.add(nums[list.peekFirst()]);
            left++;
            right++;
            while (!list.isEmpty()&&list.peekFirst()<left){
                list.pollFirst();
            }
            if(right< nums.length){
                while (!list.isEmpty()&&nums[right]>=nums[list.peekLast()]){
                    list.pollLast();
                }
            }
            list.addLast(right);
        }
        return ans.stream().mapToInt(Integer::intValue).toArray();
    }
}
